Петя Васечкин
перевёлся в другую школу. На первом уроке физкультуры ему нужно было определить
своё место в строю.
Вход. В первой строке
задано число n – количество учеников в классе.
Во второй строке
дана невозрастающая последовательность
из n натуральных чисел, описывающая рост каждого ученика в
строю.
В третьей строке
указано число x – рост Пети.
Все числа
натуральные и не превышают 200.
Выход. Выведите номер
позиции, на которую должен встать Петя.
Если в строю уже
есть ученики с таким же ростом, как у Пети, он должен встать сразу после них.
Пример
входа 1 |
Пример
выхода 1 |
8 165 163 160 160 157 157 155 154
162 |
3 |
|
|
Пример
входа 2 |
Пример
выхода 2 |
8 165 163 160 160 157 157 155 154 160 |
5 |
бинарный
поиск
Входная
последовательность уже отсортирована в невозрастающем порядке. Найдём позицию
Пети с помощью бинарного поиска по верхней границе. Нумерация позиций в строю
начинается с 1.
Реализация алгоритма
Читаем входные
данные. Заносим рост школьников в массив v.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
scanf("%d",&x);
Если в строю есть школьники с ростом, равным росту Пети, он становится
после них. Для поиска позиции Пети используем бинарный поиск по верхней границе
– это возможно, поскольку
массив отсортирован в невозрастающем порядке.
pos =
upper_bound(v.begin(),v.end(),x,greater<int>())
- v.begin();
Выводим позицию Пети, учитывая, что в задаче нумерация школьников
начинается с единицы.
printf("%d\n",pos + 1);
Реализация алгоритма – собственный бинарный поиск
Читаем входные
данные. Заносим рост школьников в массив v.
scanf("%d",&n);
v.resize(n+1);
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("%d",&x);
Петя может занять любую позицию от 1 до n + 1. Инициализируем интервал бинарного
поиска: [Left;
Right] = [1; n + 1].
int Left = 1, Right = n + 1, Middle;
Запускаем бинарный поиск.
while(Left < Right)
{
Middle = (Left + Right) / 2;
if (x <=
v[Middle]) Left = Middle + 1; else Right =
Middle;
}
Выводим ответ – позицию Пети в строю.
printf("%d\n",Left);